package com.xzz.backtrack;

import com.xzz.string.AddStrings;

import java.util.ArrayList;
import java.util.List;

/**
 * @author: hhz
 * @create: 2022-01-10 13:07
 * 306. 累加数
 * 累加数 是一个字符串，组成它的数字可以形成累加序列。
 * <p>
 * 一个有效的 累加序列 必须 至少 包含 3 个数。除了最开始的两个数以外，字符串中的其他数都等于它之前两个数相加的和。
 * <p>
 * 给你一个只包含数字'0'-'9'的字符串，编写一个算法来判断给定输入是否是 累加数 。如果是，返回 true ；否则，返回 false 。
 * <p>
 * 说明：累加序列里的数 不会 以 0 开头，所以不会出现1, 2, 03 或者1, 02, 3的情况。
 * <p>
 * result = []
 * def backtrack(路径, 选择列表):
 * if 满足结束条件:
 * result.add(路径)
 * return
 * <p>
 * for 选择 in 选择列表:
 * 做选择
 * backtrack(路径, 选择列表)
 * 撤销选择
 * <p>
 * 输入："112358"
 * 输出：true
 * 解释：累加序列为: 1, 1, 2, 3, 5, 8 。1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8
 * <p>
 * 输入："199100199"
 * 输出：true
 * 解释：累加序列为: 1, 99, 100, 199。1 + 99 = 100, 99 + 100 = 199
 **/
public class IsAdditiveNumber {
    public static void main(String[] args) {
//        System.out.println(isAdditiveNumber("112358"));
        System.out.println(isAdditiveNumber("199100199"));
        System.out.println(isAdditiveNumber("539834657215398346785398346991079669377161950407626991734534318677529701785098211336528511"));
    }

    public static boolean isAdditiveNumber(String num) {
        // 至少包含三个数
        if (num.length() < 3) return false;
        List<String> res = new ArrayList<>();
        boolean backtrack = backtrack(0, num.length(), num, res);
        System.out.println(res);
        return backtrack;
    }

    public static boolean backtrack(int start, int end, String num, List<String> list) {
        if (start == end) {
            int size = list.size();
            return size >= 3 && AddStrings.addStrings(list.get(size - 3), list.get(size - 2)).equals(list.get(size - 1));
        }
        for (int i = 0; i < num.length(); i++) {
            String curStr = num.substring(0, i + 1);
            if (curStr.length() > 1 && curStr.charAt(0) == '0') {
                continue;
            }
            String nextStr = num.substring(i + 1);
            int size = list.size();
            if (size < 2) {
                list.add(curStr);
            } else {
                if (AddStrings.addStrings(list.get(size - 2), list.get(size - 1)).equals(curStr)) {
                    list.add(curStr);
                } else {
                    continue;
                }
            }
            if (backtrack(start + curStr.length(), end, nextStr, list)) {
                return true;
            }
            list.remove(list.size() - 1);
        }
        return false;
    }
}
